
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;
int s, T, cur[N], h[N];
int n, m, k, ecnt = -1, lev[N];

struct edge{
    int v, w, nxt;
} e[N];

void AddEdge(int u, int v, int w){
    e[++ecnt] = (edge){v, w, h[u]}; h[u] = ecnt;
    e[++ecnt] = (edge){u, 0, h[v]}; h[v] = ecnt;
}

int DFS(int u, int flow){
    if(u == T) return flow;
    int res_flow = 0;
    for(int &i = cur[u]; ~i; i = e[i].nxt){
        int v = e[i].v;
        if(lev[v] == lev[u] + 1 && e[i].w > 0){
            int will_flow = DFS(v, min(flow, e[i].w));
            flow -= will_flow;
            res_flow += will_flow;
            e[i].w -= will_flow;
            e[i ^ 1].w += will_flow;
            if(!flow) break;
        }
    }
    if(!res_flow) lev[u] = -1;
    return res_flow;
}

bool BFS(){
    memset(lev, -1, sizeof(lev));
    queue<int> que;
    lev[s] = 0;
    que.push(s);
    while(!que.empty()){
        int u = que.front(); que.pop();
        for(int i = h[u]; ~i; i = e[i].nxt){
            int v = e[i].v;
            if(lev[v] == -1 && e[i].w > 0){
                lev[v] = lev[u] + 1;
                que.push(v);
            }
        }
    }
    return ~lev[T];
}

int Dinic(){
    int ans = 0;
    while(BFS()){
        memcpy(cur, h, sizeof(cur));
        ans += DFS(s, INT_MAX);
    }
    return ans;
}

int u[105], v[105];

int id(int u, int dep){
    return (dep - 1) * n + u;
}

bool check(int d){
    memset(h, -1, sizeof(h));
    ecnt = -1;
    for(int dep = 1; dep <= d; dep++){
        for(int i = 1; i <= m; i++){
            AddEdge(id(u[i], dep), id(v[i], dep), 1);
        }
    }
    
    for(int dep = 1; dep < d; dep++){
        for(int i = 1; i <= m; i++){
            AddEdge(id(u[i], dep), id(v[i], dep + 1), 1e6);
        }
        AddEdge(id(n, dep), id(n, dep + 1), 1e6);
    }
    
    s = id(1, 1);
    T = id(n, d);
    return Dinic() <= k;
}

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= m; i++){
        scanf("%d %d", &u[i], &v[i]);
    }
    
    int lb = 0, rb = n - 1;
    while(lb < rb){
        int mid = (lb + rb + 1) / 2;
        if(check(mid)) lb = mid;
        else rb = mid - 1;
    }
    
    printf("%d\n", lb);
    return 0;
}